package base.day03;

import java.util.Arrays;

/**
 * 描述：
 *      给定一个数组，求如果排序之后，相邻两数的最大差值，要求时 间复杂度O(N)，且要求不能用非基于比较的排序。
 *
 *      借助桶排序的思想，N个数设置N+1个桶，最大和最小的数分别放在最左和最右的两个桶中，中间的数按照划分的比例
 *      放入对应的桶中，中间必然有一个空桶。因此相邻数最大的差值一定不会在桶的内部两个数之间，
 *      必然在两个相邻的不为空桶的最大值和最小值之间产生。因此我们需要三个信号来记录，是否为空桶、桶的最小值，桶的最大值
 *      最后遍历桶，找出相邻桶之间的最大值，即使答案
 * @author hl
 * @version 1.0
 * @date 2020/10/25 10:43
 */
public class Code_01_MaxGap {
    public static int maxGap(int[] nums){
        if (nums == null || nums.length < 2) {
            return 0;
        }
        int len = nums.length;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < len; i++) {//找出数组的最大和最小数
            min = min > nums[i] ? nums[i] : min;
            max = max < nums[i] ? nums[i] : max;
        }
        if (min == max) {
            return 0;
        }
        boolean[] hasNum = new boolean[len + 1];
        int[] maxs = new int[len + 1];
        int[] mins = new int[len + 1];
        int bid = 0;
        for (int i = 0; i < len; i++) {
            bid =bucket(nums[i], max, min, len);
            mins[bid] = hasNum[bid] ? Math.min(mins[bid], nums[i]) : nums[i];
            maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], nums[i]) : nums[i];
            hasNum[bid] = true;
        }
        int lastMax = maxs[0];
        int res = 0;
        for (int i = 1; i <= len; i++) {
            if (hasNum[i]) {
                res = Math.max(res, mins[i] - lastMax);
                lastMax = maxs[i];
            }
        }
        return res;
    }

    public static int bucket(int num, int max, int min, int len){//获取数对应的桶的索引，最小和最大的数一定放在左右两端的桶中
        return (num - min) * len / (max - min);
    }

    // for test
    public static int comparator(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        Arrays.sort(nums);
        int gap = Integer.MIN_VALUE;
        for (int i = 1; i < nums.length; i++) {
            gap = Math.max(nums[i] - nums[i - 1], gap);
        }
        return gap;
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            if (maxGap(arr1) != comparator(arr2)) {
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    }


}
